package num51;

import org.w3c.dom.ls.LSException;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * @author : DuJiabao
 * @Date : 2021/2/8 19:01
 * @Project : sword-finger-offer
 * @File : null.java
 * @Desc : N皇后问题
 * https://leetcode-cn.com/problems/n-queens/
 * 解法: 很巧妙地利用剪枝的方法.通过三个set保存所有列所有斜对面的状态,如果存在了,那就不能放,直接剪枝结束.
 * 通过递归前的状态设置及递归后的状态清理,实现多个状态的遍历.很聪明!很有启发!
 */
class Solution {
  List<List<String>> res = new ArrayList<>();
  HashSet<Integer> cols = new HashSet<>();
  HashSet<Integer> lds = new HashSet<>();
  HashSet<Integer> rds = new HashSet<>();
  int size;

  public static void main(String[] args) {
    Solution solution = new Solution();
    List<List<String>> lists = solution.solveNQueens(4);
    System.out.println(lists.toString());
  }

  public List<List<String>> solveNQueens(int n) {
    size = n;
    int[] state = new int[n];
    Arrays.fill(state, -1);
    nQueens(0, state);
    return res;
  }

  private void nQueens(int level, int[] currentState) {
    // 结束条件
    if (level >= size) {
      generateResult(currentState);
      return;
    }
    for (int i = 0; i < size; i++) {
      if (!cols.contains(i) && !lds.contains(level + i) && !rds.contains(i - level)) {
        // 状态设置
        currentState[level] = i;
        cols.add(i);
        lds.add(level + i);
        rds.add(i - level);
        // 递归
        nQueens(level + 1, currentState);
        // 状态清理
        currentState[level] = -1;
        cols.remove(i);
        lds.remove(level + i);
        rds.remove(i - level);
      }
    }
  }

  private void generateResult(int[] state) {
    List<String> temp = new ArrayList<>();
    for (int s : state) {
      char[] row = new char[size];
      Arrays.fill(row, '.');
      row[s] = 'Q';
      temp.add(new String(row));
    }
    res.add(temp);
  }
}
